#include <bits/stdc++.h>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode() :val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* swapPairs(ListNode* head) {
    // recursion
    if(head == nullptr || head->next == nullptr) return head;
    ListNode *newHead = head->next;
    head->next = swapPairs(newHead->next);
    newHead->next = head;
    return newHead;
}

ListNode *swapPairs(ListNode *head) {
    // iterative
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *cur = dummy;
    while(cur->next != nullptr && cur->next->next != nullptr) {
        ListNode *node1 = cur->next;
        ListNode *node2 = cur->next->next;
        cur->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        cur = node1;
    }
    ListNode *ans = dummy->next;
    delete dummy;
    return ans;
}
